package KS;

import java.util.Scanner;

public class KruskalTree {


    private int count;        // 边的数量edge count
    private String[] tops;       // 顶点集合
    private int[][] mMatrix;    // 邻接矩阵
    private static final int N = 9999999;   // 最大值
    double value;


    /**
     * 创建图(用已提供的矩阵)
     *
     * 参数说明：
     *     vexs  -- 顶点数组
     *     matrix-- 矩阵(数据)
     */


    public KruskalTree(String[] vexs, int[][] matrix) {
        // 初始化"顶点数"和"边数"
        int vlen = vexs.length;
        // 初始化"顶点"
        tops = new String[vlen];
        for (int i = 0; i < tops.length; i++) {
            tops[i] = vexs[i];
        }

        // 初始化"边"
        mMatrix = new int[vlen][vlen];
        for (int i = 0; i < vlen; i++) {
            for (int j = 0; j < vlen; j++) {
                mMatrix[i][j] = matrix[i][j];
            }
        }

        // 统计"边"
        count = 0;
        for (int i = 0; i < vlen; i++) {
            for (int j = i + 1; j < vlen; j++) {
                if (mMatrix[i][j] != N) {
                    count++;
                }
            }
        }


    }




    /**
     * 返回ch位置
     */
    private int getPosition(String ch) {
        for (int i = 0; i < tops.length; i++) {
            if (tops[i] == ch) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 打印矩阵队列图
     */
    public void print() {
        System.out.printf("Martix Graph:\n");
        for (int i = 0; i < tops.length; i++) {
            for (int j = 0; j < tops.length; j++)
                System.out.printf("%10d ", mMatrix[i][j]);
            System.out.printf("\n");
        }
    }


    /**
     * 克鲁斯卡尔（Kruskal)最小生成树
     */
    public void kruskal() {
        int index = 0;                      // rets数组的索引
        int[] tends = new int[count];     // 用于保存"已有最小生成树"中每个顶点在该最小树中的终点。
        EData[] rets = new EData[count];  // 结果数组，保存kruskal最小生成树的边
        EData[] edges;                      // 图对应的所有边

        // 获取"图中所有的边"
        edges = getEdges();
        // 将边按照"权"的大小进行排序(从小到大)
        sortEdges(edges, count);

        for (int i = 0; i < count; i++) {
            int p1 = getPosition(edges[i].start);      // 获取第i条边的"起点"的序号
            int p2 = getPosition(edges[i].end);        // 获取第i条边的"终点"的序号

            int m = getEnd(tends, p1);                 // 获取p1在"已有的最小生成树"中的终点
            int n = getEnd(tends, p2);                 // 获取p2在"已有的最小生成树"中的终点


            // 如果m!=n，意味着"边i"与"已经添加到最小生成树中的顶点"没有形成环路
            if (m != n) {//没有形成环路
                // 设置m就是在"已有的最小生成树"中终点集合的索引，它的值就是终点n，
                //例如 C D线段 ,m的值就是C在tends集合中的索引位置，n就是D在tends集合中m索引位置的值
                tends[m] = n;
                rets[index++] = edges[i];           // 保存结果，保存kruskal最小生成树的边
            }
        }
        Scanner sc  = new Scanner(System.in);

        // 统计并打印"kruskal最小生成树"的信息
        int length = 0;
        for (int i = 0; i < index; i++) {
            length += rets[i].weight;//权值累加
        }

        for (int i = 0; i < index; i++) {


            System.out.println("在 "+rets[i].start+" 和 "+rets[i].end+ " 之间连接线路，其的路径长度为："+rets[i].weight+"km");

        }
        System.out.printf("最小路程为=%dKM\n ", length);
        System.out.println("请输入每千米线路的价格（单位为万元）：");
        value = sc.nextDouble();
        System.out.println("造价为"+value*length+"万元");

        System.out.printf("\n");
        System.out.println("---------------------------------------------");
    }

    /**
     * 获取图中的边
     */
    private EData[] getEdges() {
        int index = 0;
        EData[] edges;

        edges = new EData[count];
        //统计了一半的三角形，因为无向图是对称的，
        for (int i = 0; i < tops.length; i++) {
            for (int j = i + 1; j < tops.length; j++) {
                if (mMatrix[i][j] != N) {
                    edges[index++] = new EData(tops[i], tops[j], mMatrix[i][j]);
                }
            }
        }

        return edges;
    }

    /**
     * 对边按照权值大小进行排序(由小到大)
     * 通过中介变量，交换权值，
     */
    private void sortEdges(EData[] edges, int elen) {

        for (int i = 0; i < elen; i++) {
            for (int j = i + 1; j < elen; j++) {
                if (edges[i].weight > edges[j].weight) {
                    // 交换"边i"和"边j"
                    EData tmp = edges[i];
                    edges[i] = edges[j];
                    edges[j] = tmp;
                }
            }
        }
    }

    /**
     * 获取i的终点，第一次选取的点，并没有终点，因为默认的元素都是0
     */
    private int getEnd(int[] tends, int i) {
        while (tends[i] != 0) {
            i = tends[i];
        }
        return i;
    }


    // 边的结构体
    private static class EData {
        String start; // 边的起点
        String end;   // 边的终点
        int weight; // 边的权重

        public EData(String start, String end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }



        public void show() {
            String[] vexs = {"北京", "武汉","杭州", "长沙", "重庆", "上海", "南京", "西安","广水", "深圳"};
            int matrix[][]=new int[][]{
                    {0, N, 40, 80, N, N, N, N, N, N},
                    {N, 0, N, 70, 60, N, 20, 20, N, N},
                    {40, N, 0, N, 20, 80, N, N, N, N},
                    {80, 70, N, 0, 90, N, N, N, N, N},
                    {N, 60, 20, 20, 0, N, N, N, N, N},
                    {N, N, 80, N, N, 0, 40, N, 10, N},
                    {N, 20, N, N, N, 40, 0, 50, N, N},
                    {N, 20, N, N, N, N,50, 0, 60, 90},
                    {N, N, N, N, N, 10, N, 60, 0, 70},
                    {N, N, N, N, N, N, N, 90, 70, 0}};

            KruskalTree pG = new KruskalTree(vexs, matrix);

            pG.kruskal();   // Kruskal算法生成最小生成树
        }


    }



}